package leetcode;

/*
给定一个二维的矩阵，包含 X 和 O（字母 O）。

找到所有被 X 围绕的区域，并将这些区域里所有的 O 用 X 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X
 */
public class problems_130{
    public static void main(String[] arge) {
        final char X = 'X';
        final char O = 'O';
        final char P = 'P';
        char[][] test = {
//                {X, X, X, X},
//                {X, O, O, X},
//                {X, X, O, X},
//                {X, O, X, X}
        };
        new Solution().solve(test);

//        int m = test.length;
//        int n = test[0].length;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.print(test[i][j] + " ");
//            }
//            System.out.println();
//        }
//
//        System.out.println();
    }

    /**
     * 首先，不会变成X的O只可能是从边缘延伸出去的O，其他的全部都是X，所以，将边缘（有生路）的对象开始，延伸变成P，然后O变X，P变O就好
     */
    static class Solution {
        final char X = 'X';
        final char O = 'O';
        final char P = 'P';
        int m = 0;
        int n = 0;
        public void solve(char[][] board) {
            if(null == board || board.length == 0 || board[0].length == 0) return ;
            m = board.length;
            n = board[0].length;
            // 对象遍历用
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (!(i == 0 || j == 0 || i == m - 1 || j == n - 1)) {
                        continue;
                    }
                    // 对边缘点开始遍历
                    findNode(board, i, j);
                }
                System.out.println();
            }

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if(board[i][j] == O ) board[i][j] = X;
                    if(board[i][j] == P ) board[i][j] = O;
                }
            }
        }
        // 寻找有生路的点
        public void findNode(char[][] board, int i, int j) {
            if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] == P || board[i][j] == X) {
                return;
            }
            board[i][j] = P;
            findNode(board, i-1, j);
            findNode(board, i, j-1);
            findNode(board, i+1, j);
            findNode(board, i, j+1);

        }
    }
}
